Various programming languages, such as ML, C#, and Java, are constructed in a way that allows allocation of memory to be controlled by programmers, but performs de-allocation automatically by runtime mechanisms. The majority of these runtime systems employ a garbage collector, which traces object references during execution in order to find objects which are no longer being used and de-allocate and reuse their memory. However, most garbage-collection systems suffer from defects. Chief among these are the introduction of a runtime execution cost and a lag time between the time an object's memory could be reclaimed and when the garbage collector manages to find the object.
As an alternative, some systems employ a region-based memory management system. In a region-based scheme, regions are allocated in memory for objects to be placed into, and memory de-allocation happens for entire regions rather than at an object-level. Region-based memory management reduces overhead by reducing the number of memory allocations for which the runtime environment must keep track and consolidates memory de-allocation that a garbage collector might do in a piecemeal fashion. One example of region's utility is upon a call to a method which creates data structures for its execution, but which then deletes those data structures when it returns. In this situation, each region used by the method can be created when the method is called, and then deleted at the point the method is returned.
Because the number of regions is usually smaller than the total number of objects allocated, a runtime system using region-based memory management need only keep record of the number of references to objects in a region. This allows the runtime system to de-allocate a region immediately when the reference count reaches zero. This avoids the constant searching involved in garbage collection and reduces lag time for memory reclamation.
However, traditional region-based memory management systems introduce additional overhead costs of their own. Many existing systems determine at compile-time precisely when regions are allocated or de-allocated. In order to facilitate this statically-determined memory management, some of these systems force allocation and de-allocation of regions into a last-in, first-out (or stack) model. This type of system, however, reduces memory allocation efficiency by severely restricting the order in which regions can be de-allocated.
In other existing systems, no allocation order is set, but additional overhead costs are created because the system requires that objects passed to methods be passed along with whatever regions contain objects that may be used in the method. One of these, RegJava, a Java language extension by Christiansen and Velschow, requires that when an object is passed to a method that every subclass of the object's class be known and annotated in the source code. This is done in order to ensure that at compilation every region possibly referenced by the passed object is available to be passed to the called method. Because subclasses frequently contain fields that their superclasses do not, this means that many regions can possibly be referenced by an object of a given superclass. This can result in large numbers of regions being passed as method parameters. This additional argument-passing can exceed the number of registers available, adding more overhead to the runtime stack, and thus reducing or eliminating the efficiencies provided by a region-based system. What is needed is a system that can dynamically discover regions which contain referenced objects.